import model.*;

import java.util.*;

public final class MyStrategy implements Strategy {
    private final Random random = new Random();
    static CellType[][] field;
    static int n;
    static int m;
    static int[][] dist;
    static Pair[][] from;

    class Pair implements Comparable<Pair> {
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        boolean equals(Pair p) {
            return x == p.x && y == p.y;
        }

        public int compareTo(Pair p) {
            if (x != p.x) {
                return x - p.x;
            }
            return y - p.y;
        }

        int x;
        int y;
    }

    private void makeBfs(Trooper self, World world, Game game, Move move) {
        int x = self.getX();
        int y = self.getY();
        boolean[][] was = new boolean[n][m];
        boolean[][] cells = new boolean[n][m];

        for (Trooper trooper : world.getTroopers()) {
            cells[trooper.getX()][trooper.getY()] = true;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!field[i][j].equals(CellType.FREE)) {
                    cells[i][j] = true;
                }
            }
        }

        dist = new int[n][m];
        from = new Pair[n][m];
        for (int i = 0; i < n; i++) Arrays.fill(dist[i], -1);
        for (int i = 0; i < n; i++) Arrays.fill(from[i], null);

        dist[x][y] = 0;
        Queue<Pair> queue = new LinkedList<Pair>();

        queue.add(new Pair(x, y));
        int[] dx = {-1, 0, 0, 1};
        int[] dy = {0, -1, 1, 0};
        Direction[] dirs = {Direction.WEST, Direction.NORTH, Direction.SOUTH, Direction.EAST};

        while (!queue.isEmpty()) {
            Pair p = queue.poll();
            for (int i = 0; i < 4; i++) {
                int xx = p.x + dx[i];
                int yy = p.y + dy[i];
                if (xx >= 0 && xx < n && yy >= 0 && yy < m && !cells[xx][yy] && dist[xx][yy] == -1) {
                    dist[xx][yy] = dist[p.x][p.y] + 1;
                    from[xx][yy] = new Pair(p.x, p.y);
                    queue.add(new Pair(xx, yy));
                }
            }
        }
    }


    private void genericMove(Trooper self, World world, Game game, Move move) {
        field = world.getCells();
        n = field.length;
        m = field[0].length;
        if (tryShoot(self, world, game, move)) {
            return;
        }
    }

    List<Pair> getNeighbours(Pair p) {
        List<Pair> res = new ArrayList<Pair>();
        int[] dx = {-1, 0, 0, 1};
        int[] dy = {0, -1, 1, 0};
        for (int i = 0; i < 4; i++) {
            int x = p.x + dx[i];
            int y = p.y + dy[i];
            if (x >= 0 && y >= 0 && x < n && y < m) {
                res.add(new Pair(x, y));
            }
        }
        return res;
    }

    private boolean tryGrenade(Trooper self, World world, Game game, Move move) {
        if (!self.isHoldingGrenade()) {
            return false;
        }
        if (self.getActionPoints() < game.getGrenadeThrowCost()) {
            return false;
        }

        Set<Pair> teammates = new TreeSet<Pair>();
        for (Trooper trooper : world.getTroopers()) {
            if (trooper.isTeammate()) {
                teammates.add(new Pair(trooper.getX(), trooper.getY()));
            }
        }


        for (Trooper trooper : world.getTroopers()) {
            if (trooper.isTeammate()) {
                continue;
            }
            if ((trooper.getX() - self.getX()) * (trooper.getX() - self.getX()) + (trooper.getY() - self.getY()) * (trooper.getY() - self.getY()) > 25) {
                continue;
            }
            boolean ok = true;
            for (Pair p : getNeighbours(new Pair(trooper.getX(), trooper.getY()))) {
                if (teammates.contains(p)) {
                    ok = false;
                }
            }
            if (!ok) {
                continue;
            }
            move.setAction(ActionType.THROW_GRENADE);
            move.setX(trooper.getX());
            move.setY(trooper.getY());
        }
        return false;
    }

    private boolean tryShoot(Trooper self, World world, Game game, Move move) {
        if (tryGrenade(self, world, game, move)) {
            return true;
        }
        boolean shot = false;
        for (Trooper trooper : world.getTroopers()) {
            if (!trooper.isTeammate() && world.isVisible(self.getShootingRange(), self.getX(), self.getY(), self.getStance(), trooper.getX(), trooper.getY(), trooper.getStance())) {
                if (self.getActionPoints() >= self.getShootCost()) {
                    move.setAction(ActionType.SHOOT);
                    move.setX(trooper.getX());
                    move.setY(trooper.getY());
                    shot = true;
                }
            }
        }
        return shot;
    }


    int curCommanderGoal = 1;

    private void moveCommander(Trooper self, World world, Game game, Move move) {
        int[] commanderGoalXs = {3, 14, 27, 14, 27, 14, 3, 14, 3, 14, 27, 14, 3, 14, 27, 14};
        int[] commanderGoalYs = {3, 8, 17, 8, 3, 8, 17, 8, 3, 8, 3, 8, 17, 8, 17, 14};

        for (int i = 0; i < commanderGoalXs.length; i++) {
            int xx = commanderGoalXs[i];
            int yy = commanderGoalYs[i];
            if (!field[xx][yy].equals(CellType.FREE)) {
                int newX = 100000;
                int newY = 100000;
                for (int dx = -10; dx <= 10; ++dx) {
                    for (int dy = -10; dy <= 10; ++dy) {

                        if (xx + dx < 0) {
                            continue;
                        }
                        if (yy + dy < 0) {
                            continue;
                        }
                        if (xx + dx >= n) {
                            continue;
                        }
                        if (yy + dy >= m) {
                            continue;
                        }
                        if (!field[xx + dx][yy + dy].equals(CellType.FREE)) {
                            continue;
                        }
                        if (Math.abs(dx) + Math.abs(dy) < Math.abs(newX - xx) + Math.abs(newY - yy)) {
                            newX = xx + dx;
                            newY = yy + dy;
                        }
                    }
                }
                commanderGoalXs[i] = newX;
                commanderGoalYs[i] = newY;
            }
        }
        if (self.getX() == commanderGoalXs[curCommanderGoal] && self.getY() == commanderGoalYs[curCommanderGoal]) {
            curCommanderGoal++;
        }
        List<Direction> path = getPath(commanderGoalXs[curCommanderGoal], commanderGoalYs[curCommanderGoal]);
        move.setAction(ActionType.MOVE);
        move.setDirection(path.get(0));
    }

    Direction getDirection(int x1, int y1, int x2, int y2) {
        if (x1 == x2) {
            return y2 > y1 ? Direction.SOUTH : Direction.NORTH;
        }
        return x2 > x1 ? Direction.EAST : Direction.WEST;
    }

    List<Direction> getPath(int x, int y) {
        List<Direction> l = new ArrayList<Direction>();
        int curX = x;
        int curY = y;
        while (from[curX][curY] != null) {
            int tmpX = from[curX][curY].x;
            int tmpY = from[curX][curY].y;
            l.add(getDirection(tmpX, tmpY, curX, curY));
            curX = tmpX;
            curY = tmpY;
        }
        Collections.reverse(l);
        return l;
    }


    private void moveFieldMedic(Trooper self, World world, Game game, Move move) {
        genericMove(self, world, game, move);
    }

    private void moveScout(Trooper self, World world, Game game, Move move) {
        genericMove(self, world, game, move);
    }

    private void moveSniper(Trooper self, World world, Game game, Move move) {
        genericMove(self, world, game, move);
    }

    private void moveSoldier(Trooper self, World world, Game game, Move move) {
        genericMove(self, world, game, move);
    }

    @Override
    public void move(Trooper self, World world, Game game, Move move) {
        field = world.getCells();
        n = field.length;
        m = field[0].length;
        makeBfs(self, world, game, move);
        if (self.getType().equals(TrooperType.COMMANDER)) {
            moveCommander(self, world, game, move);
        } else if (self.getType().equals(TrooperType.FIELD_MEDIC)) {
            moveFieldMedic(self, world, game, move);
        } else if (self.getType().equals(TrooperType.SCOUT)) {
            moveScout(self, world, game, move);
        } else if (self.getType().equals(TrooperType.SNIPER)) {
            moveSniper(self, world, game, move);
        } else if (self.getType().equals(TrooperType.SOLDIER)) {
            moveSoldier(self, world, game, move);
        }
    }
}